
/**
 *  动态规划: 动规基础、背包问题、打家劫舍、股票问题、子序列问题；
 *  解题步骤：
 *  1、 dp数组定义以及下标的含义；
 *  2、 递推公式；
 *  3、 dp数据如何初始化；
 *  4、 遍历顺序；
 *  5、 打印dp数组；
 * 概念：
 * 01 背包：在指定容量，对应容量只能使用1次，求指定容量下物品的最大价值
 * 完全背包：在指定容量，对应容量可以多次使用，求指定容量下物品的最大价值
 * 
 */
function dynamicProgramming () {
    // 509.求斐波那契数
    const fib = (n) => {
        let dp = new Array(n + 1).fill(0) //dp数组,状态转移
        dp[0] = 0, dp[1] = 1   //初始化
        for (let i = 2; i <= n; i++) {  //遍历
            dp[i] = dp[i - 1] + dp[i - 2] // 递推公式
        }
        return dp[n]
    }

    // 70.爬楼梯
    const climbStairs = (n) => {
        // 数组下标表示每走一阶的方法
        const dp = new Array(n + 1).fill(0)
        dp[1] = 1, dp[2] = 2
        for (let i = 3; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }

    // 746.使用最小花费爬楼梯
    const minCostClimbingStairs = (cost) => {
        // 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
        // 跳到每一阶梯的最小花费,阶梯0、阶梯1 最少花费0
        const len = cost.length, dp = new Array(len + 1).fill(0)
        for (let i = 2; i <= len; i++) {
            // 台阶2
            // 从 台阶1 起跳 = 台阶1最少花费 + 台阶1 往上跳所需要的花费
            // 从 台阶0 起跳 = 台阶0最少花费 + 台阶0 往上跳所需要的花费
            dp[i] = Math.min((dp[i - 2] + cost[i - 2]), (dp[i - 1] + cost[i - 1]))
        }
        return dp[len]
    }

    // 62.不同路径
    const uniquePaths = (m, n) => {
        // dp 数组表示每一格有多少路径，
        // 机器人每次只能向下或者向右移动一步
        // 第一行，第一列每格只能从左边或从上面走过来，故初始化都为1
        const dp = new Array(m).fill(0).map(() => Array(n).fill(1))
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }

    // 63.不同路径II
    const uniquePathsWithObstacles = (obstacleGrid) => {
        const m = obstacleGrid.length, n = obstacleGrid[0].length
        const dp = new Array(m).fill(0).map(() => Array(n).fill(0))
        //  初始化第一行的路径
        for (let i = 0; i < n; i++) {
            if (obstacleGrid[0][i]) break; //如当前有障碍物,不能走,后续的路径0
            dp[0][i] = 1
        }
        // 初始化第一列的路径
        for (let i = 0; i < n; i++) {
            if (obstacleGrid[i][0]) break; //如当前有障碍物,不能走,后续的路径0
            dp[i][0] = 1
        }
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                if (!obstacleGrid[i][j]) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }

    // 343.整数拆分
    const integerBreak = function (n) {
        const dp = new Array(n + 1).fill(0)  //dp[i]表示每个数拆分获取的乘积最大值
        dp[2] = 1   //定义初始边界值,dp[0],dp[1]不能拆分,故初始值为1
        for (let i = 3; i <= n; i++) {
            for (let j = 1; j <= i >> 1; j++) {
                // 1.当 i 拆成 j 和 i-j, i-j 不再拆分的时候, 此时的乘积是 j * (i-j);
                // 2.当 i 拆成 j 和 i-j, i-j 继续拆分,此时的乘积则是 j * dp[i-j],dp[i-j]表示拆分的数的最大值;
                dp[i] = Math.max(j * (i - j), j * dp[i - j], dp[i])
            }
        }
        return dp[n]
    };

    // 96.不同的二叉搜索树
    const numTrees = function (n) {
        // 下标i表示:有i个节点对应的可以构成二叉树的种数
        let dp = new Array(n + 1).fill(0)
        // 0、1 个节点可以构成1个节点
        dp[0] = 1, dp[1] = 1
        // 2个节点只能构成左节点1个或者右节点一个
        for (let i = 2; i <= n; i++) {
            for (let j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j]
            }
        }
        return dp[n]
    };

    //------------------------01背包问题----------------------------------

    // 背包问题==> 求给定容量下,可装的最大价值
    const getMaxValue = function (bags, capacity) {
        // bags为二维数组[[1,15],[3,25],[4,30]],bags[i]指对应包的最大容量和最大价值,bag[0]表示容量为1,可装的价值是15  
        // dp[i]表示对应容量可装的最大价值
        let dp = new Array(capacity + 1).fill(0)
        // 无需初始化,容量为0只能装0
        for (let i = 0; i < bags.length; i++) {
            let [c, v] = bags[i] // 对应包的容量和价值
            for (let j = capacity; j >= c; j--) {
                dp[j] = Math.max(dp[j], dp[j - c] + v)
            }
        }
        return dp[capacity]
    }

    // 416.分割等和子集
    const canPartition = function (nums) {
        // 分成两个子集,相当于每个子集是sum/2 ---> 背包的容量为 sum/2 , 是否可以装满 ?
        let target = nums.reduce((p, c) => p + c, 0) / 2
        if (!Number.isInteger(target)) return false
        const len = nums.length, dp = new Array(target + 1).fill(0)
        for (let i = 0; i < len; i++) {
            for (let j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], (dp[j - nums[i]] + nums[i]))
                if (dp[j] == target) return true
            }
        }
        return false
    };

    // 1049.最后一块石头的重量II
    const lastStoneWeightII = function (stones) {
        // 可以分成两堆,每一堆取最接近一半的重量 
        const sum = stones.reduce((p, c) => p + c, 0), target = sum >> 1;
        let dp = new Array(target + 1).fill(0)
        for (let i = 0; i < stones.length; i++) {
            for (let j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
            }
        }
        // dp[target] 表示分成一堆的最大重量 
        return sum - dp[target] - dp[target]
    };

    // 494.目标和
    const findTargetSumWays = function (nums, target) {
        // 将所有元素的和 sum 分成两个子集,一个子集是+正数的元素和 pSum,另一个子集是-负数的元素和 nSum
        // pSum + nSum = sum  ---> 此处跟正负数没有关系,其表示元素和 
        // pSum - nSum = target
        // pSum = (sum + target)/2 
        let sum = nums.reduce((p, c) => p + c, 0)
        if (Math.abs(target) > sum) return 0
        let pSum = (sum + target) / 2
        if (!Number.isInteger(pSum)) return 0  //  ----> 正数的元素和必须为整数
        const len = nums.length, dp = new Array(pSum + 1).fill(0) // --> dp[j]表示装满当前容量有多少种方法
        dp[0] = 1 // ---> 装满容量为 0 的只有一种方法,什么都不装
        for (let i = 0; i < len; i++) {
            for (let j = pSum; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]]
            }
        }

        return dp[pSum]
    }

    // 474.一和零
    const findMaxForm = function (strs, m, n) {
        // dp[i][j] 表示背包容量为[i][j]最多可以放的物品
        let dp = new Array(m + 1).fill(0).map(() => Array(n + 1).fill(0))

        for (let str of strs) {
            let x = 0, y = 0
            for (let ch of str) {
                if (ch == '0') x++
                else y++
            }
            for (let i = m; i >= x; i--) {
                for (let j = n; j >= y; j--) {
                    dp[i][j] = Math.max(dp[i - x][j - y] + 1, dp[i][j])
                }
            }
        }

        return dp[m][n]
    }

    // -------------------- 完全背包问题 ------------------------

    // 518.零钱兑换II
    var change = function (amount, coins) {
        //  零钱 j 有 dp[j] 种方法
        const dp = new Array(amount + 1).fill(0)
        dp[0] = 1

        for (let coin of coins) {
            for (let i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin]
            }
        }

        return dp[amount]
    }

    // 377.组合总和Ⅳ
    const combinationSum4 = function (nums, target) {
        const dp = new Array(target + 1).fill(0)
        dp[0] = 1
        for (let i = 1; i <= target; i++) {
            for (let n of nums) {
                if (n > i) continue
                dp[i] += dp[i - n]
            }
        }
        return dp[target]
    };

    // 322.零钱兑换
    const coinChange = function (coins, amount) {
        // 兑换零钱 i 所对应的 最少面额组合
        let dp = new Array(amount + 1).fill(-1)
        dp[0] = 0

        for (let coin of coins) {
            for (let i = coin; i <= amount; i++) {
                // dp[i - coin] == -1 无法兑换对应的面额
                if (dp[i - coin] == -1) continue
                // 判断兑换对应面额的数量+1
                if (dp[i] == -1) dp[i] = dp[i - coin] + 1
                else dp[i] = Math.min(dp[i - coin] + 1, dp[i])
            }
        }

        return dp[amount]
    };

    // 279.完全平方数
    const numSquares = function (n) {
        // 对应i 最少有dp[i]完全平方数组成
        const dp = new Array(n + 1).fill(0)
        // 初始化
        for (let i = 1; i <= n; i++) dp[i] = i
        
        for (let i = 2; i <= n >> 1; i++) {
            let sq = i * i
            for (let j = sq; j <= n; j++) {
                dp[j] = Math.min(dp[j - sq] + 1, dp[j])
            }
        }

        return dp[n]
    };

}